import random
import matplotlib.pyplot as plt
import time
import numpy as np


"""------------------------------------------快速排序算法 非递归版---------------------------------------------------""" 
# 分组函数
def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1
# 非递归快排主体
def quickSort(arr):
    if len(arr) <= 1:
        return arr

    stack = [(0, len(arr) - 1)]
    while stack:
        low, high = stack.pop()
        if low < high:
            pivot_index = partition(arr, low, high)
            # 将右半部分的子数组压入栈
            stack.append((pivot_index + 1, high))
            # 将左半部分的子数组压入栈
            stack.append((low, pivot_index - 1))
    return arr



# 运行算法并测试时间
def run_algorithm(algorithm, data): 
    start_time = time.time()
    algorithm(data)
    end_time = time.time()
    return (end_time - start_time) * 1000

# 针对numpy的算法时间测量函数
def run_algorithm_numpy(data): 
    arr = np.array(data)
    start_time = time.time()
    arr.sort()
    end_time = time.time()
    return (end_time - start_time) * 1000


# 生成11 个大小为10^6的整数数据集，第𝑖个子集中存在元素重复106 ×10 × i %,i = 0,1,2, ⋯ ,10
N = 10000
data_sets = []
for i in [0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0]:
    m = N - int(N * i)  # 不重复的元素个数
    n = int(N * i)  # 重复元素个数
    A_m = []  # 不重复元素集合
    A_n = []  # 重复元素集合
    while len(A_m) < m:
        l = random.randint(0, N)
        if l not in A_m:
            A_m.append(l)  # “不重复的元素”必须保证不与“重复元素”相重复
    k = random.randint(0, N)
    A_n = [k] * n
    A_mn = A_m + A_n
    random.shuffle(A_mn)
    
    data_sets.append(A_mn)
    A_m = []
    A_n = [] #清空列表
    
    
# 运行不同size下的算法并记录时间
sizes = [len(data)-len(set(data))+1 for data in data_sets]
time1 = [run_algorithm(quickSort, data) for data in data_sets] # 非递归快排
time2 = [run_algorithm_numpy(data) for data in data_sets] # numpy的排序算法

# 画出不同size的运行时间变化图
plt.plot(sizes, time1, '-o',label = 'quicksort method')
plt.plot(sizes, time2, '-o',label = 'numpy method')
plt.legend()
plt.xlabel("Data Size")
plt.ylabel("Time (ms)")
plt.title("time cost of QuickSort method")
# plt.savefig("QuickSort.png") #用于保存图片
plt.show()
